// 采用c++17版本(/std:c++17)
#include "memory_manage.h"

// 构造函数
memory_manage::memory_manage(int L, int M, int N)
{
    pages.clear();
    pros.clear();
    page_number.clear();
    group_pros.clear();
    pages_to_load.clear();
    pro_pages.clear();
    // valid_page.clear();

    // 时间初始化
    io_time = 0;
    compute_time = 0;
    group_time = 0;
    // 存储初始化
    page_n = 0;
    total_size = L;
    capacity = -1;
    current_pages = 0;
    memory = M;
    page_size = gcd(total_size, memory);
    // 进程初始化
    pro_n = N;
    finished_pro = -1;
    visit_times.resize(pro_n, {-1, -1});
    pro_pages.resize(pro_n);
}

// 析构函数
memory_manage::~memory_manage() {}

// 添加进程
void memory_manage::push_procdure(int a, int b, int c, int d)
{
    pros.push_back({a, b, c, d});
}

// 页面相关设置
void memory_manage::set_page(vector<int> group)
{
    int new_page_size = gcd(total_size, memory);
    int new_page_n = page_n;
    int new_capacity = -1;
    vector<page> new_pages;
    new_pages.clear();

    for (auto x : group)
    {
        new_page_size = gcd(new_page_size, pros[x].get_ms());
        new_page_size = gcd(new_page_size, pros[x].get_ml());
    }

    new_page_n = (total_size + new_page_size - 1) / new_page_size;
    new_capacity = memory / new_page_size;
    new_pages.resize(new_page_n);

    // 如果是第一次设置页面
    if (group[0] == 0)
    {
        page_size = new_page_size;
        page_n = new_page_n;
        capacity = new_capacity;
        pages = new_pages;

        int idx = 0;
        // 为每个页面设置起始和终止地址
        for (auto &p : pages)
        {
            p.set_begin(idx);
            p.set_end(idx + page_size - 1);
            idx += page_size;
        }
    }
    // 更改页面
    else
    {
        if (!((page_size > new_page_size) && (page_size % new_page_size == 0))) // 若页面不可分割，则调整
        {
            new_page_size = gcd(new_page_size, page_size);
            if (new_page_size == page_size)
                return;
            new_page_n = (total_size + new_page_size - 1) / new_page_size;
            new_capacity = memory / new_page_size;
            new_pages.resize(new_page_n);
        }
        int t = page_size / new_page_size;
        current_pages *= t; // 修改当前页面数

        int addr = 0;
        for (int i = 0; i < page_n; i++)
        {
            for (int j = 0; j < t; j++)
            {
                new_pages[i * t + j].set_begin(addr);
                new_pages[i * t + j].set_end(addr + new_page_size);
                new_pages[i * t + j].set_in_use(pages[i].is_in_use());
                new_pages[i * t + j].set_valid(pages[i].is_valid());
                addr += new_page_size;
            }
        }

        page_size = new_page_size;
        page_n = new_page_n;
        capacity = new_capacity;
        pages = new_pages;
    }

    // 设置每个待处理进程所需的所有页面
    int start, end;
    int b, e;
    for (int i = 0; i < pro_n; i++)
    {
        pro_pages[i].clear();
        start = pros[i].get_ms();
        end = start + pros[i].get_ml() - 1;
        b = start / page_size;
        e = end / page_size;
        for (int j = b; j <= e; j++)
        {
            pro_pages[i].push_back(j);
        }
    }
    return;
}

// 返回第 n 个进程所需页号
vector<int> memory_manage::get_numbers(int n)
{
    return pro_pages[n];
}

// OPT 页面置换算法
int memory_manage::select(int index)
{
    // 优先选出当前在内存且空闲的页面集合
    vector<int> mem_pages;
    mem_pages.clear();
    for (int i = 0; i < page_n; ++i)
    {
        if (pages[i].is_valid() && !pages[i].is_in_use())
            mem_pages.push_back(i);
    }
    // 如果内存中空闲页面只有一个，看下一个进程是否需要它，不需要则换
    if (mem_pages.size() == 1)
    {
        vector<int> next;
        if (index == pro_n)
            next = get_numbers(pro_n - 1);
        else
            next = get_numbers(index);
        if (find(next.begin(), next.end(), mem_pages[0]) != next.end()) // 下一个进程会用到该页，该页已在内存中，无需换出
            return -1;
        return mem_pages[0];
    }
    // 页面选择，
    int result = -1;
    int farthest_time = -1;
    // OPT，选择最久不被用到的页面换出
    // 遍历页面
    for (int page_id : mem_pages)
    {
        int next_use = INT_MAX;
        // 最后一个进程了
        if (index == pro_n)
        {
            vector<int> next = get_numbers(pro_n - 1);
            if (find(next.begin(), next.end(), page_id) == next.end()) // 这个进程未用到该页，该页已在内存中，无需换出
                return page_id;
            continue;
        }
        // 遍历进程
        for (int j = index; j < pro_n; ++j)
        {
            vector<int> fut = get_numbers(j);
            if (find(fut.begin(), fut.end(), page_id) != fut.end()) // 找到了
            {
                next_use = pros[j].get_ts();
                break;
            }
        }
        // 若该页面以后再也不会被用到
        if (next_use == INT_MAX)
            return page_id;
        // 寻找最久不被用到的页面
        if (next_use > farthest_time)
        {
            farthest_time = next_use;
            result = page_id;
        }
    }

    return result;
}
// 修改页面的in_use，即释放内存中time时刻已完成进程的页面
void memory_manage::release_finished_pages(int current_time)
{
    if (finished_pro == -1)
        return;
    for (int j = finished_pro; j < pro_n; ++j)
    {
        int endt = visit_times[j].second;
        if (endt != -1 && endt <= current_time)
        {
            // 进程j已结束，释放它的所有页面
            vector<int> nums = get_numbers(j);
            for (int num : nums)
                pages[num].set_in_use(false);
            finished_pro = j;
        }
    }
}
// 进程分组，与进程idx开始时间相同的进程为一组，并行执行
vector<int> memory_manage::get_group(int &pro_idx)
{
    group_time = compute_time;
    int group_start = pros[pro_idx].get_ts();
    vector<int> group_pros;
    group_pros.clear();
    int j = pro_idx;
    while (j < pro_n && pros[j].get_ts() == group_start)
    {
        group_pros.push_back(j);
        ++j;
    }
    pro_idx = j;

    // 组内按 visit 时长降序（time_length）排序索引
    sort(group_pros.begin(), group_pros.end(), [&](int a, int b)
         { return pros[a].get_tl() > pros[b].get_tl(); });
    return group_pros;
}
// 获得pages_to_loads
void memory_manage::get_pages_to_load()
{
    pages_to_load.clear();
    for (int num : page_number)
    {
        if (!pages[num].is_valid())
            pages_to_load.push_back(num);
    }
}
// 打印输出
void memory_manage::off_print(vector<int> &offload_pages)
{
    if (!offload_pages.empty())
    {
        int start_page = offload_pages[0];
        int last_page = start_page;

        for (int k = 1; k <= offload_pages.size(); ++k)
        {
            bool is_break =
                (k == offload_pages.size()) ||
                (offload_pages[k] != last_page + 1);

            if (is_break)
            {
                int begin_addr = pages[start_page].get_begin();
                int block_size = (last_page - start_page + 1) * page_size;

                cout << "Offload " << io_time << " "
                     << begin_addr << " "
                     << block_size << endl;

                io_time += 40 * block_size;
                offload_pages.erase(offload_pages.begin(), offload_pages.begin() + last_page - start_page + 1);
                start_page = 0;
                if (k < offload_pages.size())
                    start_page = offload_pages[k];
            }

            if (k < offload_pages.size())
                last_page = offload_pages[k];
        }

        release_finished_pages(io_time);
    }
}
// 换出页面
void memory_manage::page_offload(int idx)
{

    int pages_needed = pages_to_load.size();           // 需要加载页的个数
    int pages_to_load_size = pages_needed * page_size; // 需要加载的总大小
    int pages_to_load_start = 0;                       // 需要加载页的起始地址

    if (!pages_to_load.empty()) // 不为空，即需要换页
        pages_to_load_start = pages[pages_to_load[0]].get_begin();
    else // 为空，不需要换页
        return;

    vector<int> offload_pages;
    set<int> remain;
    offload_pages.clear();
    remain.clear();

    // 持续换出页面，直至能装入所有pages_to_load页
    while (current_pages + pages_needed > capacity)
    {
        // 尝试释放空闲内存
        release_finished_pages(io_time);

        // 检查内存中是否存在空闲页
        bool check = false;
        for (int p = 0; p < page_n; ++p)
        {
            if (pages[p].is_valid() && !pages[p].is_in_use() && !remain.count(p))
            {
                check = true;
                remain.insert(p);
                break;
            }
        }
        // 内存中所有页都在被访问，必须等待
        if (!check)
        {
            off_print(offload_pages);
            // 内存中所有页都在被访问，必须等待最早结束的访问
            int earliest_end = INT_MAX;
            for (int j = finished_pro; j < pro_n; ++j)
            {
                if (visit_times[j].second > io_time)
                {
                    earliest_end = min(earliest_end, visit_times[j].second);
                }
            }
            if (earliest_end != INT_MAX)
                io_time = earliest_end;
            // 释放那些在新 io_time 已结束的页面
            release_finished_pages(io_time);
            continue;
        }
        // 存在空闲页
        int target = select(idx);
        if (target < 0)
            continue;

        offload_pages.push_back(target);
        pages[target].set_valid(false);
        current_pages--;

       
    }
    off_print(offload_pages);
}
// 页面换入
void memory_manage::page_reload()
{
    // 若有尚未换入内存的页面
    if (!pages_to_load.empty())
    {
        int space = capacity - current_pages - 1; // 能换进的页面数量

        int start_page = pages_to_load[0];
        int last_page = start_page;

        for (int k = 1; k <= pages_to_load.size(); ++k)
        {
            bool is_break = (k == pages_to_load.size()) || (pages_to_load[k] != last_page + 1) || (space == 0);
            if (is_break)
            {
                int begin = pages[start_page].get_begin();
                int size1 = (last_page - start_page + 1) * page_size;
                cout << "Reload " << io_time << " "
                     << begin << " "
                     << size1 << endl;
                io_time += 40 * size1;
                current_pages += last_page - start_page + 1;
                pages_to_load.erase(pages_to_load.begin(), pages_to_load.begin() + last_page - start_page + 1);
                for (int p = start_page; p <= last_page; ++p)
                    pages[p].set_valid(true);
                if (space == 0) // 内存已满，不能再调入
                    return;
                if (k < pages_to_load.size())
                    start_page = pages_to_load[k];
            }
            if (k < pages_to_load.size())
            {
                last_page = pages_to_load[k];
                space--;
            }
        }
    }
    release_finished_pages(io_time);
}
// 进程执行
void memory_manage::pro_execute(int idx)
{
    int visit_start = max({pros[idx].get_ts(), io_time, group_time});
    int visit_end = visit_start + pros[idx].get_tl();
    for (int num : page_number)
    {
        // 征用这些页面
        if (num >= 0 && num < page_n)
            pages[num].set_in_use(true);
    }

    cout << "Visit " << visit_start << " " << idx << endl;
    visit_times[idx] = {visit_start, visit_end};
    compute_time = max(compute_time, visit_end);
}
void memory_manage::run()
{
    // 按顺序处理进程
    int i = 0;
    while (i < pro_n)
    {
        // 进程分组
        group_pros = get_group(i);
        set_page(group_pros);
        // 处理组内进程
        for (int idx : group_pros)
        {
            // 获得该进程需要的页
            page_number = get_numbers(idx);
            // 需要加载的页（不在内存中的）
            get_pages_to_load();
            // 若内存未满，则调入页面
            if (current_pages < capacity)
                page_reload();
            // 内存已满，换出页面
            if (current_pages == capacity)
                page_offload(i);
            // 换入剩余的页
            page_reload();
        }
        for (int idx : group_pros)
            // 进程执行，同一计算任务一起执行
            pro_execute(idx);
        if (i == 1)
            finished_pro = 0;
    }
    cout << "Fin " << max(io_time, compute_time) << endl;
}